#include <stdio.h>
#include <stdlib.h>

inline int ran(int l, int u)
{
	return l + random() % (u - l);
}

inline void swap(int *a, int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void quick_sort(int *data, int l, int u)
{
	int i, j, t, s;
	
	i = l;
	j = u + 1;

	if (data == NULL)
		return;
	if (l >= u)
		return;
	
	t = ran(l, u);
	s = data[t];
	swap(data + l, data + t);
	while (1) {
		do i++; while (i <= u && data[i] < s);
		do j--; while (data[j] > s);
		if (i >= j)
			break;
		swap(data + i, data + j);
	}
	swap(data + l, data + j);

	quick_sort(data, l, j - 1);
	quick_sort(data, j + 1, u);
}

int main()
{
	int data[] = {9, 8, 7, 6, 5, 4, 3, 2, 1};
	int i, l = 0, u = 8;
	quick_sort(data, l, u);

	for (i = 0; i < 9; i++) {
		printf("%d ", data[i]);
	}
	printf("\n");
	return 0;
}
